package sort;

import java.util.Arrays;

/**
 * @Author: fzykd
 * Date: 2024-04-17
 * Time: 21:35
 * User: LQH
 */


//插入排序 在原有序的区间中 找到合适的位置 插入区间外的数  就像打扑克理牌一样
public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {12, 15, 9, 20, 6, 31, 24};

        //插入排序 一开始就要有一个区间
        //认为第一个元素 就是一个区间 就是有序的  从第二个元素开始插入所以 i从1开始
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i]; //定义待插入的元素
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            //j回退到了 小于0的地方
            arr[j+1] = tmp;
        }

        System.out.println(Arrays.toString(arr));

    }

}
